with Ada.Unchecked_Deallocation;

generic

   type Value_Type is private;

package List is
   -- Type for list objects
   type List_Type is limited private;
   -- Used to define where to insert an element relative to
   -- the given index (see : Insert routine)
   type Positioning_Type is (Head, Before, After, Tail);
   -- Raised if a routine is supplied with an index that
   -- is < 1 or > Length (list)
   Index_Out_Of_Bounds     : exception;
   -- Removes all elements from a list and frees all resources.
   procedure Clear (List   : in out List_Type);
   -- Inserts a value in the given list at position index.
   -- If the value is inserted before or after the index is
   -- determined by the positioning attribute. If positioning
   -- is Head or Tail, the index is ignored. If the list is
   -- empty Index_Out_Of_Bounds exception is raised.
   procedure Insert
     (List                 : in out List_Type;
      Value                : in Value_Type;
      Index                : in Natural;
      Positioning          : in Positioning_Type);
   -- Appends a value to the end of the list.
   procedure Append
     (List                 : in out List_Type; Value : in Value_Type);
   -- Adds a value to the beginning of a list.
   procedure Prepend
     (List                 : in out List_Type; Value : in Value_Type);
   -- Returns a list's value that is stored at index.
   function Value
     (List                 : in List_Type;
      Index                : in Natural)
 return Value_Type;
   -- Removes a value that is stored at index in the list.
   procedure Remove
     (List                 : in out List_Type; Index : in Natural);
   -- Returns the number of items in the list.
   function Length (List   : in List_Type) return Natural;
private

   type List_Element_Type;
   type List_Element_Ref_Type is access all List_Element_Type;
   type List_Element_Type is record
      Value  : Value_Type;
      Prev   : List_Element_Ref_Type := null;
      Next   : List_Element_Ref_Type := null;
   end record;
   type List_Type is record
      Head   : List_Element_Ref_Type := null;
      Tail   : List_Element_Ref_Type := null;
      Length : Natural := 0;
   end record;

   procedure Free is new Ada.Unchecked_Deallocation
     (Object => List_Element_Type, Name => List_Element_Ref_Type);

end List;
